Shift operations are common in computer arithmetic logic units (ALUs). Different types of shifts are possible as, for example, an arithmetic shift which is used to multiply or divide a binary value by a factor which is a power of two while preserving the arithmetic sign of the value. Other types of shifts are logical shifts which serve to move bit patterns of the binary value or word to the left or right within the word so that, for example, a series of bits can be repositioned from the lower half of the word to the upper half of the word.
As shown in FIG. 1A, a typical shifter will have an input 10 for loading a binary word into the shifter and an output 20 for outputing a shifted binary word to external hardware. The loading of the input binary word is performed in parallel so that, in the example of a 64 bit shifter, all 64 bits of the input binary word will be loaded into the shifter at once. Similarly, the output of the shifter usually matches in number the number of input lines (one line per bit) in the input binary word. Thus, a 64 bit shifter will also have 64 bits of parallel output.
A shifter also includes control signals 30 for performing the loading of the input binary word and performing the shifting of the binary word by a specified number of bits, either right or left. Also, new data such as a bit value to take the place of a bit value being shifted away from either the left or right edges of the computer word within the shifter can be specified. The shifter output will typically reflect the current state of the computer word being shifted.
In order for a microprocessor shifter to be fully functional, every shifter output bit needs access to every shifter input bit and the sign or zero bit. The sign bit is the leftmost bit in arithmetic shift instructions while the zero bit is the input value used for logical shift operations to fill a leftmost or rightmost bit position in a word being shifted.
The most straightforward method of shifting binary values is with a single large array arrangement of transistor "cells." For example, FIG. 1B depicts a typical array of NMOS pass gates 100 for a simple 4-bit shifter capable of shifting up to 3 bit positions. The wires and transistors are drawn as they would be drawn in the physical shifter layout. Data flows through the shifter from top to bottom. Inputs 102 correspond to the four bits in the input word and are designated IN(O), IN(1), IN(2) and IN(3). Inputs 102 enter the "top" of the shifter and are generated by external circuitry (not shown). Outputs 104 are designated OUT(0), OUT(1), OUT(2) and OUT(3). Outputs 104 flow out the bottom of the shifter. For simplicity, the required control lines are not shown in FIG. 1B.
In order for each output bit to have access to each input bit, each vertical input line 106, 108, 110 and 112, must extend horizontally across the entire width of the shifter as shown by horizontal data lines 114, 116, 118 and 120. For an N-bit shifter, N horizontal input data lines would be required. In order to shift by any shift amount ("SA") up to 3, a pass-gate from each horizontal data line to each vertical output line is required. Sixteen pass gates such as pass gate 122 are shown connecting horizontal data lines 114, 116, 118 and 120 with vertical output lines 105, 107, 109 and 111, respectively. Note that since the control lines are not shown, there is no connection to the gate of pass gate 122. And, in order for each output to have access to the sign-or-zero bit on line 124, we need a vertical sign-or-zero line per bit as shown by vertical sign-or-zero lines 126, 128, 130 and 132, and a pass gate, such as pass gate 134, from the vertical sign-or-zero ("SOZ") lines to their corresponding output line. In order to minimize the number of different control signals that need to be generated, there is a SOZ passgate (from the vertical SOZ line to the corresponding output line) for each data passgate (from the horizontal data line to the vertical output line). In this way, the multiple passgates which connect each vertical SOZ line to the corresponding output line perform an OR function, and the same control signals can be used for both the data passgates and the SOZ passgates.
The physical structure depicted in FIG. 1B is undesirable because of the large number of transistors (N.times.N.times.2 for an N-wide shifter) and control lines required. Thus, most shifter structures implement some kind of pre-muxing.
The typical 64 bit shifter described here uses a multiplexer to shift the input data by the shift amount modulo 4 (hereinafter "(SA MOD 4)"). Then this pre-shifted data is input to the shifter array. The shifter array shifts the pre-shifted data by (SA DIV 4).times.4 bits, where the "DIV" operation is the integer result (i.e., less the remainder) of dividing the first operand ("SA", in this case) by the second operand ("4", in this case). The total shift is then ((SA MOD 4)+(SA DIV 4).times.4 bits. For example, for SA=50, the pre-mux would shift the input data by (50 MOD 4)=2. Then the shifter array would shift the pre-shifted data by (50 DIV 4).times.4=12.times.4=48 bits, for a total shift of 50 bits. The advantage of pre-muxing is that it greatly simplifies the required array structure. In this array structure, the output line of each bit, bit need only access: 1) the pre-shifted data for every 4th bit slice, and 2) the sign-or-zero bit.
FIG. 2 shows pre-multiplexing (or "pmux") cell 140. Pmux 140 is a 7:1 mux which is drawn as it would be oriented in the physical shifter layout. Inputs of pmux 140 include the input bit for a particular bit slice, IN(n), and the input bits for the 3 bit slices to each side. Pmux output 142 is the vertical input data line of the shifter array.
FIG. 3 shows basic cell 150 of a shifter array used with pre-multiplexing cells such as pmux 140 of FIG. 2. Basic cell 150 is drawn in the orientation it would appear in a physical silicon chip embodiment. Basic cell 150 is 4 bits wide and tall. Four horizontal lines 152, 154, 156 and 158 are 4 input data lines ("D-lines"). Four vertical lines 160, 162, 164 and 166 are 4 output data lines ("On-lines"). Four vertical sign-or-zero ("SOZ" ) lines 168, 170, 172 and 174 are also shown. Select data ("SD") line 176 controls the selection of input data (from the D-lines) onto the corresponding O-lines. Select sign-or-zero ("SS") line 178 controls the selection of the SOZ data onto the corresponding O-lines. The 64-bit shifter array is a 16.times.16 array of the basic cell 150 of FIG. 3.
FIG. 4 shows a 4-bit slice 200 of the 64-bit shifter pre-multiplexer and shifter array. The 4 bit slice consists of 4 horizontal pmux cells 202, 204, 206 and 208 and 16 1. vertical basic cells 210. The 64-bit shifter consists of 16 of these 4-bit slices 200.
FIG. 5 shows a diagram of the entire 64-bit shifter array and how the D-lines start out vertical and then become horizontal. Sample instances of 4-bit nibbles of vertical D-lines are shown at 222 and 224. In actuality there are sixteen nibbles of vertical D-lines, one for each nibble column such as nibble column at 230. Sample instances of the basic cells are shown at 226 and 228. For clarity, the transistors in the basic cells are not shown.. In actuality there are 16.times.16 basic cells in the array. The 4 diagonal dots in basic cell 226 and basic cell 228 represent the "vias" where the vertical D-lines meet the horizontal D-lines. Even if the input data to the array is pre-multiplexed, each output bit of the array must still have access to every 4th input bit. Thus, 64 continuous horizontal input data lines are required. Note that because of the pre-multiplexing, this array structure requires only (256.times.4).times.2=2048 transistors to implement; this is 1/4 of the 64.times.64.times.2=8096 transistors which an array with no pre-muxing would require.
FIG. 6 shows a diagram of the required control lines for the entire shifter array. 31 control signals are necessary to implement the full functionality of the 64-bit typical shifter. Each diagonal line actually represents a pair of lines. The first signal in the pair connects to the SD line of a basic cell; the second signal in the pair connects to the SS line of a basic cell.
The control signals depicted in FIG. 7 are defined as shown in Table 1.
TABLE 1 ______________________________________ L15 = "1" if Shift Left and (SA DIV 4) = 15 L14 = "1" if Shift Left and (SA DIV 4) = 14 L13 = "1" if Shift Left and (SA DIV 4) = 13 L12 = "1" if Shift Left and (SA DIV 4) = 12 L11 = "1" if Shift Left and (SA DIV 4) = 11 L10 = "1" if Shift Left and (SA DIV 4) = 10 L9 = "1" if Shift Left and (SA DIV 4) = 9 L8 = "1" if Shift Left and (SA DIV 4) = 8 L7 = "1" if Shift Left and (SA DIV 4) = 7 L6 = "1" if Shift Left and (SA DIV 4) = 6 L5 = "1" if Shift Left and (SA DIV 4) = 5 L4 = "1" if Shift Left and (SA DIV 4) = 4 L3 = "1" if Shift Left and (SA DIV 4) = 3 L2 = "1" if Shift Left and (SA DIV 4) = 2 L1 = "1" if Shift Left and (SA DIV 4) = 1 L0 = "1" if Shift Left and (SA DIV 4) = 0 or Shift Right and (SA DIV 4) = 0 R15 = "1" if Shift Right and (SA DIV 4) = 15 R14 = "1" if Shift Right and (SA DIV 4) = 14 R13 = "1" if Shift Right and (SA DIV 4) = 13 R12 = "1" if Shift Right and (SA DIV 4) = 12 R11 = "1" if Shift Right and (SA DIV 4) = 11 R10 = "1" if Shift Right and (SA DIV 4) = 10 R9 = "1" if Shift Right and (SA DIV 4) = 9 R8 = "1" if Shift Right and (SA DIV 4) = 8 R7 = "1" if Shift Right and (SA DIV 4) = 7 R6 = "1" if Shift Right and (SA DIV 4) = 6 R5 = "1" if Shift Right and (SA DIV 4) = 5 R4 = "1" if Shift Right and (SA DIV 4) = 4 R3 = "1" if Shift Right and (SA DIV 4) = 3 R2 = "1" if Shift Right and (SA DIV 4) = 2 R1 = "1" if Shift Right and (SA DIV 4) = 1 ______________________________________